#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>

using namespace std;

// 接雨水
// 岛屿的数量
// 寻找峰值
// 无重复字符的最长子串
// 相交链表

// 接雨水 ---- 动态规划/双指针
// 对于下标i,下雨后水能到达的最大高度等于下标i两边的最大高度的最小值
// 下标i处能接的雨水量等于下标i处的水能到达的最大高度减去height[i]
// 对于数组 height 中的每个元素，分别向左和向右扫描并记录左边和右边的最大高度
// 然后计算每个下标位置能接的雨水量

// 动态规划
class Solution
{
public:
    int trap(vector<int> &height)
    {
        int n = height.size();
        if (n == 0)
            return 0;

        // 下标i及左边的最大值
        vector<int> leftMax(n);
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++)
        {
            leftMax[i] = max(leftMax[i - 1], height[i]);
        }

        // 下标i及右边的最大值
        vector<int> rightMax(n);
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--)
        {
            rightMax[i] = max(rightMax[i + 1], height[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            ans += min(leftMax[i], rightMax[i]) - height[i];
        }

        return ans;
    }
};

// 双指针
// 即i处接的水量=min(ileftMax, irightMax)-height[i]，这个公式本身是没有问题的。
// 观察这个公式，我们可以发现，最终拿来计算的是两边最大值的相对较小值
// 我们只需要得知较小值就行了，并不一定真的需要知道较大值是什么。

class Solution
{
public:
    int trap(vector<int> &height)
    {
        int n = height.size();
        if (n == 0)
            return 0;

        int ans = 0, left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        while (left < right)
        {
            // 先计算左右两边的最大值
            leftMax = max(leftMax, height[left]);
            rightMax = max(rightMax, height[right]);
            if (height[left] < height[right])
            {
                ans += leftMax - height[left];
                left++;
            }
            else
            {
                ans += rightMax - height[right];
                right--;
            }
        }

        return ans;
    }
};

class Solution
{
public:
    int trap(vector<int>& height)
    {
        // 我们使用两个变量来标记前缀和后缀的最大值
        // 我们可以计算前缀值和后缀值中较小值的那边的体积
        int n = height.size();
        int prev_max = 0,suf_max = 0;
        int ret = 0;
        int left = 0,right = n-1;
        while(left <= right)
        {
            prev_max = max(prev_max,height[left]);
            suf_max = max(suf_max,height[right]);
            if(prev_max < suf_max)
            {
                ret += prev_max - height[left];
                left++;
            }
            else
            {
                ret += suf_max - height[right];
                right--;
            }
        }

        return ret;
    }
};

// 岛屿的数量
// 广度优先遍历
class Solution
{
public:
    int m, n;
    bool vis[301][301];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int ans = 0;
    int numIslands(vector<vector<char>> &grid)
    {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1' && !vis[i][j])
                {
                    ans++;
                    bfs(grid, i, j);
                }
            }
        }

        return ans;
    }

    void bfs(vector<vector<char>> &grid, int i, int j)
    {
        queue<pair<int, int>> q;
        q.push({i, j});
        vis[i][j] = true;

        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
                {
                    q.push({x, y});
                    vis[x][y] = true;
                }
            }
        }
    }
};

// 深度优先遍历
class Solution
{
public:
    int m, n;
    bool vis[301][301];
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int ans = 0;
    int numIslands(vector<vector<char>> &grid)
    {
        m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (grid[i][j] == '1' && !vis[i][j])
                {
                    ans++;
                    dfs(grid, i, j);
                }
            }
        }

        return ans;
    }

    void dfs(vector<vector<char>> &grid, int i, int j)
    {
        vis[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            int x = i + dx[k], y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && !vis[x][y])
            {
                dfs(grid, x, y);
            }
        }
    }
};

// 寻找峰值
// 二分查找变体，在二分查找时，取中间位置m，并与它相邻位置m+1进行比较
// 如果m大于m+1，说明峰值应该在左侧，否则应该在右侧，移动对应的左右边界。
class Solution
{
public:
    int findPeakElement(vector<int> &nums)
    {
        int left = 0, right = nums.size() - 1;
        while (left < right)
        {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[mid + 1])
            {
                right = mid;
            }
            else
            {
                left = mid + 1;
            }
        }

        return left;
    }
};

// 无重复字符的最长子串  滑动窗口
class Solution
{
public:
    int lengthOfLongestSubstring(string s)
    {
        unordered_map<char, int> hash;
        int n = s.size(), left = 0, right = 0, ans = 0;
        while (right < n)
        {
            hash[s[right]]++;
            while (hash[s[right]] > 1)
            {
                hash[s[left]]--;
                left++;
            }
            ans = max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
};

// 相交链表
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 哈希表
class Solution
{
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
    {
        // 使用哈希表
        if (headA == nullptr || headB == nullptr)
            return nullptr;
        unordered_set<ListNode *> hash;
        ListNode *cur = headA;
        while (cur)
        {
            hash.insert(cur);
            cur = cur->next;
        }
        cur = headB;
        while (cur)
        {
            if (hash.count(cur))
            {
                return cur;
            }
            cur = cur->next;
        }

        return nullptr;
    }
};
